极值|容忍度_基于AI算法的数据库异常监测系统的设计与实现

篇首语：本文由编程笔记#小编为大家整理，主要介绍了基于AI算法的数据库异常监测系统的设计与实现相关的知识，希望对你有一定的参考价值。

美团数据库平台研发组&＃xff0c;面临日益急迫的数据库异常发现需求&＃xff0c;为了更加快速、智能地发现、定位和止损&＃xff0c;我们开发了基于AI算法的数据库异常检测服务。本文从特征分析、算法选型、模型训练与实时检测等维度介绍了我们的一些实践和思考&＃xff0c;希望为从事相关工作的同学带来一些启发或者帮助。

1. 背景

数据库被广泛用于美团的核心业务场景上&＃xff0c;对稳定性要求较高&＃xff0c;对异常容忍度非常低。因此&＃xff0c;快速的数据库异常发现、定位和止损就变得越来越重要。针对异常监测的问题&＃xff0c;传统的固定阈值告警方式&＃xff0c;需要依赖专家经验进行规则配置&＃xff0c;不能根据不同业务场景灵活动态调整阈值&＃xff0c;容易让小问题演变成大故障。

而基于AI的数据库异常发现能力&＃xff0c;可以基于数据库历史表现情况&＃xff0c;对关键指标进行7 * 24小时巡检&＃xff0c;能够在异常萌芽状态就发现风险&＃xff0c;更早地将异常暴露&＃xff0c;辅助研发人员在问题恶化前进行定位和止损。基于以上这些因素的考量&＃xff0c;美团数据库平台研发组决定开发一套数据库异常检测服务系统。接下来&＃xff0c;本文将会从特征分析、算法选型、模型训练与实时检测等几个维度阐述我们的一些思考和实践。

2. 特征分析

2.1 找出数据的变化规律

在具体进行开发编码前&＃xff0c;有一项非常重要的工作&＃xff0c;就是从已有的历史监控指标中&＃xff0c;发现时序数据的变化规律&＃xff0c;从而根据数据分布的特点选取合适的算法。以下是我们从历史数据中选取的一些具有代表性的指标分布图&＃xff1a;

从上图我们可以看出&＃xff0c;数据的规律主要呈现三种状态&＃xff1a;周期、漂移和平稳^[1]。因此&＃xff0c;我们前期可以针对这些普遍特征的样本进行建模&＃xff0c;即可覆盖大部分场景。接下来&＃xff0c;我们分别从周期性、漂移性和平稳性这三个角度进行分析&＃xff0c;并讨论算法设计的过程。

2.1.1 周期性变化

1. 提取趋势成分&＃xff0c;分离出残差序列。使用移动平均法提取出长期趋势项&＃xff0c;跟原序列作差得到残差序列&＃xff08;此处周期性分析与趋势无关&＃xff0c;若不分离趋势成分&＃xff0c;自相关将显著受到影响&＃xff0c;难以识别周期&＃xff09;。
2. 计算残差的循环自相关&＃xff08;Rolling Correlation&＃xff09;序列。通过循环移动残差序列后&＃xff0c;与残差序列进行向量点乘运算来计算自相关序列&＃xff08;循环自相关可以避免延迟衰减&＃xff09;。
3. 根据自相关序列的峰值坐标来确定周期T。提取自相关序列的一系列局部最高峰&＃xff0c;取横坐标的间隔为周期&＃xff08;如果该周期点对应的自相关值小于给定阈值&＃xff0c;则认为无显著周期性&＃xff09;。

具体过程如下&＃xff1a;

2.1.2 漂移性变化

对于待建模的序列&＃xff0c;通常要求它不存在明显的长期趋势或是存在全局漂移的现象&＃xff0c;否则生成的模型通常无法很好地适应指标的最新走势^[2]。我们将时间序列随着时间的变化出现均值的显著变化或是存在全局突变点的情况&＃xff0c;统称为漂移的场景。为了能够准确地捕捉时间序列的最新走势&＃xff0c;我们需要在建模前期判断历史数据中是否存在漂移的现象。全局漂移和周期性序列均值漂移&＃xff0c;如下示例所示&＃xff1a;

数据库指标受业务活动等复杂因素影响&＃xff0c;很多数据会有非周期性的变化&＃xff0c;而建模需要容忍这些变化。因此&＃xff0c;区别于经典的变点检测问题&＃xff0c;在异常检测场景下&＃xff0c;我们只需要检测出历史上很平稳&＃xff0c;之后出现数据漂移的情况。综合算法性能和实际表现&＃xff0c;我们使用了基于中位数滤波的漂移检测方法&＃xff0c;主要的流程包含以下几个环节&＃xff1a;

1. 中位数平滑

   a.根据给定窗口的大小&＃xff0c;提取窗口内的中位数来获取时序的趋势成分。

   b.窗口需要足够大&＃xff0c;以避免周期因素影响&＃xff0c;并进行滤波延迟矫正。

   c.使用中位数而非均值平滑的原因在于为了规避异常样本的影响。

2. 判断平滑序列是否递增或是递减

   a.中位数平滑后的序列数据&＃xff0c;若每个点都大于&＃xff08;小于&＃xff09;前一个点&＃xff0c;则序列为递增&＃xff08;递减&＃xff09;序列。

   b.如果序列存在严格递增或是严格递减的性质&＃xff0c;则指标明显存在长期趋势&＃xff0c;此时可提前终止。

3. 遍历平滑序列&＃xff0c;利用如下两个规则来判断是否存在漂移的现象

   a.当前样本点左边序列的最大值小于当前样本点右边序列的最小值&＃xff0c;则存在突增漂移&＃xff08;上涨趋势&＃xff09;。

   b.当前样本点左边序列的最小值大于当前样本点右边序列的最大值&＃xff0c;则存在突降漂移&＃xff08;下跌趋势&＃xff09;。

2.1.3 平稳性变化

对于一个时序指标&＃xff0c;如果其在任意时刻&＃xff0c;它的性质不随观测时间的变化而变化&＃xff0c;我们认为这条时序是具备平稳性的。因此&＃xff0c;对于具有长期趋势成分亦或是周期性成分的时间序列而言&＃xff0c;它们都是不平稳的。具体示例如下图所示&＃xff1a;

针对这种情况&＃xff0c;我们可以通过单位根检验&＃xff08;Augmented Dickey-Fuller Test&＃xff09;^[3]来判断给定的时间序列是否平稳。具体地说&＃xff0c;对于一条给定时间范围指标的历史数据而言&＃xff0c;我们认为在同时满足如下条件的情况下&＃xff0c;时序是平稳的&＃xff1a;

1. 最近1天的时序数据通过adfuller检验获得的p值小于0.05。
2. 最近7天的时序数据通过adfuller检验获得的p值小于0.05。

3. 算法选型

3.1 分布规律与算法选择

通过了解业界的一些知名公司在时序数据异常检测上公布的产品介绍&＃xff0c;加上我们历史积累的经验&＃xff0c;以及对部分线上实际指标的抽样分析&＃xff0c;它们的概率密度函数符合如下情况的分布&＃xff1a;

针对上述的分布&＃xff0c;我们调研了一些常见的算法&＃xff0c;并确定了箱形图、绝对中位差和极值理论作为最终异常检测算法。以下是对常见时序数据检测的算法对比表&＃xff1a;

我们没有选择3Sigma的主要原因是它对异常容忍度较低&＃xff0c;而绝对中位差从理论上而言具有更好的异常容忍度&＃xff0c;所以在数据呈现高对称分布时&＃xff0c;通过绝对中位差&＃xff08;MAD&＃xff09;替代3Sigma进行检测。我们对不同数据的分布分别采用了不同的检测算法&＃xff08;关于不同算法的原理可以参考文末附录的部分&＃xff0c;这里不做过多的阐述&＃xff09;&＃xff1a;

1. 低偏态高对称分布&＃xff1a;绝对中位差&＃xff08;MAD&＃xff09;
2. 中等偏态分布&＃xff1a;箱形图&＃xff08;Boxplot&＃xff09;
3. 高偏态分布&＃xff1a;极值理论&＃xff08;EVT&＃xff09;

有了如上的分析&＃xff0c;我们可以得出具体的根据样本输出模型的流程&＃xff1a;

算法的整体建模流程如上图所示&＃xff0c;主要涵盖以下几个分支环节&＃xff1a;时序漂移检测、时序平稳性分析、时序周期性分析和偏度计算。下面分别进行介绍&＃xff1a;

举例来说&＃xff0c;假设给定时序自2022/03/01 00:00:00至2022/03/08 00:00:00止&＃xff0c;给定窗口大小为5&＃xff0c;周期跨度为一天&＃xff0c;那么对于时间索引30而言&＃xff0c;对其建模所需要的样本点将来自于如下时间段&＃xff1a;

[03/01 00:25:00, 03/01 00:35:00]
[03/02 00:25:00, 03/02 00:35:00]
…
[03/07 00:25:00, 03/07 00:35:00]

4. 偏度计算。时序指标转化为概率分布图&＃xff0c;计算分布的偏度&＃xff0c;若偏度的绝对值超过阈值&＃xff0c;则通过极值理论进行建模输出阈值。若偏度的绝对值小于阈值&＃xff0c;则通过箱形图或是绝对中位差的方式进行建模输出阈值。

3.2 案例样本建模

这里选取了一个案例&＃xff0c;展示数据分析及建模过程&＃xff0c;便于更清晰的理解上述过程。其中图(a)为原始序列&＃xff0c;图(b)为按照天的跨度进行折叠的序列&＃xff0c;图©为图(b)中某时间索引区间内的样本经过放大后的趋势表现&＃xff0c;图(d)中黑色曲线为图©中时间索引所对应的下阈值。如下是针对某时序的历史样本进行建模的案例&＃xff1a;

上图©区域内的样本分布直方图以及阈值&＃xff08;已剔除其中部分异常样本&＃xff09;&＃xff0c;可以看到&＃xff0c;在该高偏分布的场景中&＃xff0c;EVT算法计算的阈值更为合理。

4. 模型训练与实时检测

4.1 数据流转过程

为了实时检测规模庞大的秒级数据&＃xff0c;我们以基于Flink进行实时流处理为出发点&＃xff0c;设计了如下的技术方案&＃xff1a;

1. 实时检测部分&＃xff1a;基于Flink实时流处理&＃xff0c;消费Mafka&＃xff08;美团内部的消息队列组件&＃xff09;消息进行在线检测&＃xff0c;结果存储于Elasticsearch&＃xff08;以下简称ES&＃xff09;中&＃xff0c;并产生异常记录。
2. 离线训练部分&＃xff1a;以Squirrel&＃xff08;美团内部的KV数据库&＃xff09;作为任务队列&＃xff0c;从MOD&＃xff08;美团内部运维数据仓库&＃xff09;读取训练数据&＃xff0c;从配置表读取参数&＃xff0c;训练模型&＃xff0c;保存于ES&＃xff0c;支持自动和手动触发训练&＃xff0c;通过定时读取模型库的方式&＃xff0c;进行模型加载和更新。

以下是具体的离线训练和在线检测技术设计&＃xff1a;

4.2 异常检测过程

异常检测算法整体采用分治思想&＃xff0c;在模型训练阶段&＃xff0c;根据历史数据识别提取特征&＃xff0c;选定合适的检测算法。这里分为离线训练和在线检测两部分&＃xff0c;离线主要根据历史情况进行数据预处理、时序分类和时序建模。在线主要加载运用离线训练的模型进行在线实时异常检测。具体设计如下图所示&＃xff1a;

5. 产品运营

为了提高优化迭代算法的效率&＃xff0c;持续运营以提高精准率和召回率&＃xff0c;我们借助Horae&＃xff08;Horae是美团内部可扩展的时序数据异常检测系统&＃xff09;的案例回溯能力&＃xff0c;实现在线检测、案例保存、分析优化、结果评估、发布上线的闭环。

目前&＃xff0c;异常检测算法指标如下&＃xff1a;

• 精准率&＃xff1a;随机选择一部分检测出异常的案例&＃xff0c;人工校验其中确实是异常的比例&＃xff0c;为81%。
• 召回率&＃xff1a;根据故障、告警等来源&＃xff0c;审查对应实例各指标异常情况&＃xff0c;对照监测结果计算召回率&＃xff0c;为82%。
• F1-score&＃xff1a;精准率和召回率的调和平均数&＃xff0c;为81%。

6. 未来展望

目前&＃xff0c;美团数据库异常监测能力已基本构建完成&＃xff0c;后续我们将对产品继续进行优化和拓展&＃xff0c;具体方向包括&＃xff1a;

1. 具有异常类型识别能力。可以检测出异常的类型&＃xff0c;如均值变化、波动变化、尖刺等&＃xff0c;支持按异常类型进行告警订阅&＃xff0c;并作为特征输入后续诊断系统&＃xff0c;完善数据库自治生态^[4]。
2. 构建Human-in-Loop环境。支持根据反馈标注自动学习&＃xff0c;保障模型持续优化^[5]。
3. 多种数据库场景的支持。异常检测能力平台化以支持更多数据库场景&＃xff0c;如DB端到端报错、节点网络监测等。

7. 附录

7.1 绝对中位差

绝对中位差&＃xff0c;即Median Absolute Deviation(MAD)&＃xff0c;是对单变量数值型数据的样本偏差的一种鲁棒性测量^[6]&＃xff0c;通常由下式计算而得&＃xff1a;

其中在先验为正态分布的情况下&＃xff0c;一般C选择1.4826&＃xff0c;k选择3。MAD假定样本中间的50%区域均为正常样本&＃xff0c;而异常样本落在两侧的50%区域内。当样本服从正态分布的情况下&＃xff0c;MAD指标相较于标准差更能适应数据集中的异常值。对于标准差&＃xff0c;使用的是数据到均值的距离平方&＃xff0c;较大的偏差权重较大&＃xff0c;异常值对结果影响不能忽视&＃xff0c;而对MAD而言少量的异常值不会影响实验的结果&＃xff0c;MAD算法对于数据的正态性有较高要求。

7.2 箱形图

箱形图主要通过几个统计量来描述样本分布的离散程度以及对称性&＃xff0c;包括&＃xff1a;

• Q₀&＃xff1a;最小值&＃xff08;Minimum&＃xff09;
• Q₁&＃xff1a;下四分位数&＃xff08;Lower Quartile&＃xff09;
• Q₂&＃xff1a;中位数&＃xff08;Median&＃xff09;
• Q₃&＃xff1a;上四分位数&＃xff08;Upper Quartile&＃xff09;
• Q₄&＃xff1a;最大值&＃xff08;Maximum&＃xff09;

将Q₁与Q₃之间的间距称为IQR&＃xff0c;当样本偏离上四分位1.5倍的IQR&＃xff08;或是偏离下四分位数1.5倍的IQR&＃xff09;的情况下&＃xff0c;将样本视为是一个离群点。不同于基于正态假设的三倍标准差&＃xff0c;通常情况下&＃xff0c;箱形图对于样本的潜在数据分布没有任何假定&＃xff0c;能够描述出样本的离散情况&＃xff0c;且对样本中包含的潜在异常样本有较高的容忍度。对于有偏数据&＃xff0c;Boxplot进行校准后建模更加符合数据分布^[7]。

7.3 极值理论

真实世界的数据很难用一种已知的分布来概括&＃xff0c;例如对于某些极端事件&＃xff08;异常&＃xff09;&＃xff0c;概率模型&＃xff08;例如高斯分布&＃xff09;往往会给出其概率为0。极值理论^[8]是在不基于原始数据的任何分布假设下&＃xff0c;通过推断我们可能会观察到的极端事件的分布&＃xff0c;这就是极值分布&＃xff08;EVD&＃xff09;。其数学表达式如下&＃xff08;互补累积分布函数公式&＃xff09;&＃xff1a;

其中t代表样本的经验阈值&＃xff0c;对于不同场景可以设置不同取值&＃xff0c;$\gamma$,$\delta$分别是广义帕累托分布中的形状参数与尺度参数&＃xff0c;在给定样本超过人为设定的经验阈值t的情况下&＃xff0c;随机变量X-t是服从广义帕累托分布的。通过极大似然估计方法我们可以计算获得参数估计值





γ


^




\\hat\\gamma


γ^​与





δ


^




\\hat\\delta


δ^ &＃xff0c;并且通过如下公式来求取模型阈值&＃xff1a;

上述公式中q代表风险参数&＃xff0c;n是所有样本数量&＃xff0c;Nt是满足x-t>0的样本数量。由于通常情况下对于经验阈值t的估计没有先验的信息&＃xff0c;因此可以使用样本经验分位数来替代数值t&＃xff0c;这里经验分位数的取值可以根据实际情况来选择。

8. 参考资料

• [1] Ren, H., Xu, B., Wang, Y., Yi, C., Huang, C., Kou, X., … & Zhang, Q. (2019, July). Time-series anomaly detection service at microsoft. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 3009-3017).
• [2] Lu, J., Liu, A., Dong, F., Gu, F., Gama, J., & Zhang, G. (2018). Learning under concept drift: A review. IEEE Transactions on Knowledge and Data Engineering, 31(12), 2346-2363.
• [3] Mushtaq, R. (2011). Augmented dickey fuller test.
• [4] Ma, M., Yin, Z., Zhang, S., Wang, S., Zheng, C., Jiang, X., … & Pei, D. (2020). Diagnosing root causes of intermittent slow queries in cloud databases. Proceedings of the VLDB Endowment, 13(8), 1176-1189.
• [5] Holzinger, A. (2016). Interactive machine learning for health informatics: when do we need the human-in-the-loop?. Brain Informatics, 3(2), 119-131.
• [6] Leys, C., Ley, C., Klein, O., Bernard, P., & Licata, L. (2013). Detecting outliers: Do not use standard deviation around the mean, use absolute deviation around the median. Journal of experimental social psychology, 49(4), 764-766.
• [7] Hubert, M., & Vandervieren, E. (2008). An adjusted boxplot for skewed distributions. Computational statistics & data analysis, 52(12), 5186-5201.
• [8] Siffer, A., Fouque, P. A., Termier, A., & Largouet, C. (2017, August). Anomaly detection in streams with extreme value theory. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1067-1075).

关于团队

美团基础技术部/数据库研发中心/数据库平台研发组&＃xff0c;负责为美团各个业务线提供高效便捷的数据库使用入口&＃xff0c;帮助美团DBA稳定快捷地维护数据库&＃xff0c;同时提供分析诊断平台&＃xff0c;实现数据库自治。

阅读美团技术团队更多技术文章合集

前端 | 算法 | 后端 | 数据 | 安全 | 运维 | iOS | Android | 测试

| 在公众号菜单栏对话框回复【2021年货】、【2020年货】、【2019年货】、【2018年货】、【2017年货】等关键词&＃xff0c;可查看美团技术团队历年技术文章合集。

| 本文系美团技术团队出品&＃xff0c;著作权归属美团。欢迎出于分享和交流等非商业目的转载或使用本文内容&＃xff0c;敬请注明“内容转载自美团技术团队”。本文未经许可&＃xff0c;不得进行商业性转载或者使用。任何商用行为&＃xff0c;请发送邮件至tech&＃64;meituan.com申请授权。